Podstawowe definicje. Etapy tworzenia programy.

Algorytm (algorithm) jest to sposób w postaci ściśle określonych reguł i metod na rozwiązanie określonego zadania w skończonej liczbie kroków.
Inaczej: Algorytm to jednoznaczny przepis, dyktujący krok po kroku sposób postępowania w celu rozwiązania pewnego problemu lub sposobu osiągnięcia jakiegoś celu.
    Ilość kroków algorytmu zależy od tego, jak złożony jest problem, którego on dotyczy. Zawsze jednak liczba tych kroków będzie liczbą skończoną. Poprawnie stworzony algorytm zapewnia uzyskanie oczekiwanego wyniku pod warunkiem, że użyjemy poprawnych danych dla konkretnego zadania. Umożliwia uzyskanie tego samego wyniku dla tych samych danych.
    Wykonawcą algorytmu może być człowiek lub komputer. Algorytm jest podstawowym pojęciem informatyki. Każdy program komputerowy jest zapisem jakiegoś algorytmu. Algorytm jest tworzony na podstawie specyfikacji problemu, który ma rozwiązywać. Dane i wyniki ze specyfikacji są jednocześnie danymi wejściowymi i danymi wyjściowymi (czyli wynikami działania) algorytmu. Od algorytmu wymaga się, aby wszystkie jego elementy (dane, polecenia, wyniki) były dobrze określone, a sam algorytm był uniwersalny. Algorytm może być zapisany słownie w postaci listy kroków lub w jednym z języków programowania - wtedy jest zrozumiały dla komputera. Może być również przedstawiony w postaci graficznej, jako schemat blokowy. Oceną szybkości działania algorytmu jest jego złożoność, czyli liczba wykonywanych operacji. W praktyce często zadowalamy się oceną efektywności działania algorytmu, czyli jak szybko działa algorytm dla konkretnych danych. Mimo że komputery są coraz szybsze, istnieją problemy, których nadal nie można rozwiązać ze względu na bardzo dużą złożoność opracowanych dla nich algorytmów.

Cechy charakterystyczne poprawnego algorytmu:

  1. Poprawność - dla każdego przypisanego zestawu danych, po wykonaniu skończonej liczby czynności, algorytm prowadzi do poprawnych wyników.
  2. Jednoznaczność - w każdym przypadku zastosowania algorytmu dla tych samych danych otrzymamy ten sam wynik.
  3. Szczegółowość - wykonawca algorytmu musi rozumieć opisane czynności i potrafić je wykonywać.
  4. Uniwersalność - algorytm ma służyć rozwiązywaniu pewnej grupy zadań, a nie tylko jednego zadania. Przykładowo algorytm na rozwiązywanie równań w postaci ax + b=0 ma je rozwiązać dla dowolnych współczynników a i b, a nie tylko dla jednego konkretnego zadania, np. 2x + 6 = 0
     

Tworząc algorytm rozwiązania jakiegoś problemu musimy sprecyzować:

  1. SPECYFIKĘ PROBLEMU (na czym polega problem)
  2. DANE (z jakich danych wyjściowych korzystamy)
  3. WYNIK (co ma być wynikiem zadania)
  4. ZWIĄZKI WYNIKU Z DANYMI (wzory, zależności, poszczególne czynności)

Przykład:
ad 1. Obliczamy pole prostokąta
ad 2. Dane: a,b – długości boków prostokąta
ad 3. Wynik: p – pole prostokąta
ad 4. Związek wyniku z danymi: p=a*b


Pod względem konstrukcyjnym algorytmy dzielimy na:

Procedura - zapis algorytmu w jakimś języku programowania.

Program -zespół kodowanych instrukcji, określający dokładnie przebieg operacji arytmetycznych i logicznych do wykonania przez komputer.

Translator - program tłumaczący program napisany w jakimkolwiek języku programowania na język wewnętrzny maszyny (maszynowy).


Rodzaje translatorów:   
Kompilator np. Turbo Pascal    • Interpretr np. HTML
Zależnie od trybu działania, proces tłumaczenia (translacji) może polegać na tłumaczeniu kodu źródłowego na kod wynikowy w całości - KOMPILACJA lub tłumaczeniu z natychmiastowym wykonaniem programu - INTERPRETACJA

Programowanie obiektowe
(ang. object-oriented programming) to metodologia tworzenia programów komputerowych, która definiuje programy za pomocą "obiektów" - elementów łączących stan (czyli dane) i zachowanie (czyli procedury, tu: metody). Obiektowy program komputerowy wyrażony jest jako zbiór takich obiektów, komunikujących się pomiędzy sobą w celu wykonywania zadań. Podejście to różni się od tradycyjnego programowania proceduralnego, gdzie dane i procedury nie są ze sobą bezpośrednio związane.
Programowanie strukturalne tworzy model składający się z zespołu procedur - czynności, które posługują się pewnymi typami danych - obiektami. Jest to model trudniejszy do zrozumienia niż w przypadku podejścia obiektowego - tu mamy pewną grupę obiektów (podobnie, jak w rzeczywistości), które wchodzą ze sobą w interakcje.

Programowanie (oraz projektowanie) obiektowe najlepiej przedstawia metafora tworzenia wioski ludzi, w której definiujemy zadania dla poszczególnych osób, oraz każemy im przekazywać informacje między sobą w określony sposób. Na przykład - tworzymy wioskę z czterech ludzi - każdy z nich potrafi wykonać jedno z podstawowych działań matematycznych. Następnie dodajemy osobę, która na podstawie skomplikowanego wzoru matematycznego zapisanego na kartce rozdzieli zadania dla tych czterech osób, oraz zbierze wyniki. Będziemy teraz mogli obliczyć wyniki wielu złożonych wzorów. Ciekawą obserwacją jest to, że żadna z osób nie mogłaby wykonać całego zadania, działając w pojedynkę. Zadanie jest wykonalne dzięki współdziałaniu w grupie.. Czyli - zdolność - potencjał grupy elementów jest czymś więcej, niż sumą zdolności - potencjałów jej poszczególnych członków. Główną siłą jest odpowiednia definicja połączeń między obiektami. Podsumowując - programowanie obiektowe jest tworzeniem modelu świata w pamięci komputera. Jest najlepszym znanym (bo najbardziej zbliżonym do rzeczywistości - a natury nikt do tej pory nie prześcignął w pomysłowości) sposobem tworzenia systemów przetwarzających informacje.
cechy:

Programowanie obiektowe zyskało status techniki dominującej w połowie lat 80-tych, głównie ze względu na wpływ C++, stanowiącego rozszerzenie języka C. Dominacja C++ została utrwalona przez wzrost popularności graficznych interfejsów użytkownika, do tworzenia których programowanie obiektowe nadaje się szczególnie dobrze.
Obiektowość rozprzestrzeniła się dość znacznie, jednak zwykle w systemach hybrydowych, w połączeniu z programowaniem niskopoziomowym (C++), funkcyjnym (Ruby, Ocaml, niektóre dialekty Lispa), sieciowym (Java), skryptowym (Perl, Python) itd.

Abstrakcja
Każdy obiekt w systemie służy jako model abstrakcyjnego "wykonawcy", który może wykonywać pracę, opisywać i zmieniać swój stan, oraz komunikować się z innymi obiektami w systemie, bez ujawniania, w jaki sposób zaimplementowano dane cechy. Procesy, funkcje lub metody mogą być również abstrahowane, a kiedy tak się dzieje, konieczne są rozmaite techniki rozszerzania abstrakcji.
Enkapsulacja
Czyli ukrywanie implementacji, hermetyzacja. Zapewnia, że obiekt nie może zmieniać stanu wewnętrznego innych obiektów w nieoczekiwany sposób. Tylko wewnętrzne metody obiektu są uprawnione do zmiany jego stanu. Każdy typ obiektu prezentuje innym obiektom swój "interfejs", który określa dopuszczalne metody współpracy. Pewne języki osłabiają to założenie, dopuszczając pewien poziom bezpośredniego (kontrolowanego) dostępu do "wnętrzności" obiektu. Ograniczają w ten sposób poziom abstrakcji.
Dziedziczenie
Porządkuje i wspomaga polimorfizm i enkapsulację dzięki umożliwieniu definiowania i tworzenia specjalizowanych obiektów na podstawie bardziej ogólnych. Dla obiektów specjalizowanych nie trzeba redefiniować całej funkcjonalności, lecz tylko tę, której nie ma obiekt ogólniejszy. W typowym przypadku powstają grupy obiektów zwane klasami, oraz grupy klas zwane drzewami. Odzwierciedlają one wspólne cechy obiektów.
Polimorfizm
Referencje i kolekcje obiektów mogą dotyczyć obiektów różnego typu, a wywołanie metody dla referencji spowoduje zachowanie odpowiednie dla pełnego typu obiektu wywoływanego. Jeśli dzieje się to w czasie działania programu, to nazywa się to późnym wiązaniem lub wiązaniem dynamicznym. Niektóre języki udostępniają bardziej statyczne (w trakcie kompilacji) rozwiązania polimorfizmu - na przykład szablony i przeciążanie operatorów w C++.

Programowanie strukturalne to paradygmat programowania zalecający hierarchiczne dzielenie kodu na moduły, które komunikują się jedynie poprzez dobrze określone interfejsy. Jest to rozszerzenie koncepcji programowania proceduralnego.
Według angielskiej wikipedii jest to raczej pewna poddyscyplina lub podzbiór programowania proceduralnego zalecająca stosowanie konstrukcji języka takich jak pętle i instrukcje warunkowe, oraz unikanie instrukcji goto i wielokrotnych punktów wejścia i wyjścia z kodu danego podbloku programu.
Programowanie proceduralne to paradygmat programowania zalecający dzielenie kodu na procedury, czyli fragmenty wykonujące ściśle określone operacje.
Procedury nie powinny korzystać ze zmiennych globalnych (w miarę możliwości), lecz pobierać i przekazywać wszystkie dane (czy też wskaźniki do nich) jako parametry wywołania. Instrukcje goto mogą być wprawdzie używane w procedurach, ale w żadnym wypadku celem wskoczenia w środek innej procedury.
 

Podstawowe paradygmaty tworzenia algorytmów komputerowych:

·               dziel i zdobywaj – dzielimy problem na kilka mniejszych i je znowu dzielimy, aż ich rozwiązaniach nie staną się oczywiste (rekurencja),

·               programowanie dynamiczne – problem dzielony jest na kilka, ważność każdego z nich jest oceniana i po pewnym wnioskowaniu wyniki analizy niektórych prostszych zagadnień wykorzystuje się do rozwiązania głównego problemu,

·               metoda zachłanna – nie analizujemy podproblemów dokładnie, tylko wybieramy najbardziej obiecującą w tym momencie drogę rozwiązania,

·               programowanie liniowe – oceniamy rozwiązanie problemu przez pewną funkcję jakości i szukamy jej minimum,

·               poszukiwanie i wyliczanie – kiedy przeszukujemy zbiór danych aż do odnalezienie rozwiązania,

·               probabilistyczne rozwiązanie – algorytm działa poprawnie z bardzo wysokim prawdopodobieństwem, ale wynik nie jest pewny,

·               heurystyka – człowiek na podstawie swojego doświadczenia tworzy algorytm, który działa w najbardziej prawdopodobnych warunkach, rozwiązanie zawsze jest przybliżone.

Najważniejsze techniki implementacji algorytmów komputerowych

·                     proceduralność – algorytm dzielimy na szereg podstawowych procedur, wiele algorytmów dzieli wspólne biblioteki standardowych procedury, z których są one wywoływane w razie potrzeby,

·                     praca po kolei – wykonywanie kolejnych procedur algorytmu, według kolejności ich wywołań, na raz pracuje tylko jedna procedura,

·                     praca równoległa – wiele procedur wykonywanych jest w tym samym czasie, wymieniają się one danymi,

·                     rekurencja – procedura wywołuje sama siebie, aż do uzyskania wyniku lub błędu,

·                     obiektowość – procedury i dane łączymy w pewne obiekty reprezentujące najważniejsze elementy algorytmu oraz stan wewnętrzny wykonującego je urządzenia.


 Schematy blokowe algorytmów.

Opis symboli graficznych schematu blokowego

Symbol

Opis działania
Oznaczenie rozpoczęcia działań przez algorytm
Blok wprowadzania i wyprowadzania danych. W bloku wprowadzania danych są one często przypisywane do zmiennych, które używane są w dalszych operacjach.
Blok podstawowy zawierający operacje lub grupę operacji na danych w wyniku których zmianie ulega np. postać danych.
 
Blok warunkowy. Na podstawie warunku sprawdzającego w tym bloku wybierana jest jedna z dwóch dróg działań algorytmu. Jedna jest wybierana wówczas, gdy warunek jest spełniony, a druga gdy nie jest spełniony.
 
Oznaczenie zakończenia działań algorytmu

Algorytm dodawania dwóch liczb


1. Pierwszym symbolem na schemacie będzie symbol rozpoczęcia działań przez algorytm /Start/
2. Algorytm rozpoczyna się od pobrania liczb, które mają zostać dodane
3. W następnym kroku algorytmu dane liczby są zsumowane.
4. Następnie podany jest wynik działania
5. Koniec algorytmu /Stop/

Pierwszy algorytm

Słowo algorytm jest łaczone z imieniem greckiego matematyka Euklidesa, żyjącego w latach około 365 - 300 r. p.n.e. Zadaniem algorytmu Euklidesa jest wyznaczenie największego wspólnego dzielnika (NWD) dwóch liczb naturalnych. Na rysunku w tzw. chmurkach objaśniono dokładnie działania.
 


Algorytm z zastosowaniem instrukcji warunkowej /parzenie herbaty/
Myślę, że to można zrozumieć. Algorytm sprawdza, czy w czajniku jest woda, jeśli jej nie ma, to kieruje do kroku "Nalej wody". Następnie, kiedy woda na pewno jest w czajniku, należy się upewnić, czy włączyłeś gaz. Jeżeli nie, to należy to zrobić, a następnie postawić czajnik na palniku (albo grzejniku, jeżeli masz kuchnię elektryczną, ale tego już nie sprawdzamy). Pozostaje czekać. Sprawdzamy, czy woda się zagotowała, jeśli nie, to czekamy dalej. Jeżeli woda się zagotowała, zalewamy herbatę. Koniec algorytmu.

 

 Podstawowe elementy języka Pascal.

Program w TP podzielony jest na:

Komentarze
W Pascalu ujmuje się je pomiędzy nawiasy klamrowe {To jest komentarz}

Deklaracja Bibliotek (modułów)
Uses dos,crt;

Deklaracja Stałych
Const     abc=500;
                komentarz='tu jest tekst';

Deklaracja zmiennych:
var x,y,z:integer;
 

 Typy danych, zastosowanie poszczególnych typów

            TYPY DANYCH:

    •
TYPY CAŁKOWITE
shortint
(-128..127) 1 bajt
integer (-32768..32767} 2 bajty
longint {-2147483648.. 2147483647} 4 bajty
byte {0..255} 1 bajt
word {0..65535} 2 bajty
    •
TYP RZECZYWISTY
real od 5.0e-324 do 1.7e308.
    •
TYP LOGICZNY
boolean - typ ten może przyjmować jedynie dwie wartości: TRUE (prawda) lub FALSE (fałsz)
    •
TYP ZNAKOWY
char - typ ten przyjmuje dowolny pojedynczy znak o kodach ASCII (0..255) np. znak "A" czy "!"
    •
TYP ŁAŃCUCHOWY
string - jest to ciąg o długości 0-255 znaków, przykładowym łańcuchem jest: 'To jest tekst', zwróć uwagę na użyte apostrofy !

 Instrukcje wyjścia, wyjścia 


Write(); - powodujewypisanie wartości wyrażenia zawartego w nawiasie.

Writeln(); - powodujewypisanie wartości wyrażenia zawartego w nawiasie i przejście do nowego wiersza.

Write(123); Writeln(x);
Writeln(‘To jest zdanie’); Write(‘Tekst’,4,’ ‘);
Write(x:4:2);



Readln(); - odczytanie danej z klawiatury i zakończonej naciśnięciem klawisza Enter.

Read(); - odczytanie danej z dysku.

Instrukcję Readln(); (bez parametru) stosujemy do zatrzymania programu. Naciśnięcie klawisza Enter powoduje dalszy ciąg programu.
 

Instrukcja przypisania.

 :=  - dwuznak nadający wartość zmiennej.

Np. Wiek := 29; Imie := ’Ola’;

 Instrukcja warunkowa. Instrukcja grupująca

if warunek then
       
instrukcja 1;
else
       
instrukcja 2;

lub
if warunek then instrukcja 1;

- instrukcja warunkowa sprawdza warunek, Jeśli jest on prawdziwy, wykonywana jest instrukcja 1, a jeśli nie instrukcja 2.

Jeśli w instrukcji warunkowej ma być wykonany blok instrukcji, to instrukcje blokujemy ogranicznikami
begin … end;.


Przykład:
1. program cw3_25;
2.     var A, B : Integer;
3. begin
4.     write ('Podaj A: '); readln (A);
5.     write ('Podaj B: '); readln (B);
6.     if (A>B) then
7.         writeln ('Najwieksza z liczb to: ', A)
8.     else
9.         writeln ('Najwieksza z liczb to: ', B);
10.   readln;
11. end.


Operatory (or, and) i ich zastosowanie w instrukcji warunkowej.

AND
Mówiąc po polsku jest to operator "I" i stosuje się tam gdzie są potrzebne spełnione dwa lub więcej warunków
OR
Mówiąc po polsku jest to operator "LUB" i stosuje się tam gdzie jest potrzebny spełniony co najmniej jeden z dwóch lub więcej warunków,
NOT
Operator negacji. Jeśli warunek jest spełniony to cały warunek z operatorem not nie jest spełniony.

 Algorytmy iterakcyjne


Pętla FOR ... TO

Stosujemy, jeśli znamy liczbę cykli pętli.
for x:=1 to 10 do instrukcja;
Algorytm wprowadzania 10 liczb do tablicy

Pętla WHILE


Jeśli nie znamy liczby wprowadzanych elementów w pętli to na końcu zbioru umieszczamy „strażnika” (wartownika).
Jogo zadaniem jest zakończenie pętli.

Możemy sprawdzać warunek przed wykonaniem cyklu pętli...
while a<>100 do instrukcja;
(dopóki a<>100 wykonuj instrukcje)
Algorytm sumowania dowolnej ilości liczb

Pętla REPEAT

... lub sprawdzać warunek po wykonaniu cyklu pętli
repeat instrukcja until a=100;
(powtarzaj instrukcje póki warunek a=100 nie jest spełniony)
 

 Typ tablicowy


Do grupowania dużej ilości informacji wymyślono AGREGATY:
 Macierze (tablice) jednowymiarowe i wielowymiarowe
 Struktury danych (rekordy)
 Relacyjne bazy danych
 Arkusze
 Tabele
 Formularze
 Zapytania
Tabela jednowymiarowa
Tabela posiada “indeksy” oraz “elementy tabeli”

1

2

3

4

5

34

56

76

3

12

Deklaracja tabeli:        var tabela: array[1..5] of real;
Wpisywanie danych:   
tabela[2]:=56;
Tabela dwuwymiarowa
Deklaracja tabeli:       
var tabelka array[1..5, 1..10] of real;
Wpisywanie danych:  
tabelka[2][3]:=56;

Program tabliczka mnożenia

1. program tabliczka;

2. var
3.      i,j: integer;
4.       d: real;
5.      tabm: array[1..10,1..10] of integer;
6. BEGIN
7. for i:=1 to 10 do
8.    for j:=1 to 10 do
9.         tabm[i,j]:=i*j;
10. writeln('Tabliczka mnożenia - drukuje...');
11. for i:=1 to 10 do
12.     begin;
13.         for j:=1 to 10 do
14.             begin;
15.                 d:=tabm[i,j];
16.                 write(d:3:0);
17.             end;
19.         writeln;
20.     end;
21. readln;
22. END.

 

Drzewko algorytmu porządkowania trzech liczb
 



Wierzchołek tego drzewa przedstawia wszystkie możliwe rozwiązania.
Drzewko służy do określenia liczby operacji wykonanych przez algorytm.
Algorytm jest optymalny, jeżeli wysokość drzewka jest najniższa. To znaczy liczba pesymistycznych porównań jest najmniejsza.

Program porządkowanie3
a,b,c – liczby nieuporządkowane
x,y,z – liczby uporządkowane

Program porzadkowanie3;
var
    a,b,c,x,y,z:integer;
begin
    write('Podaj a:'); readln(a);
    write('Podaj b:'); readln(b);
    write('Podaj c:'); readln(c);
    if a<=b then
        if c<=a then
            begin x:=c; y:=a; z:=b; end
        else
            if b<=c then
                begin x:=a; y:=b; z:=c; end
            else
                begin x:=a; y:=c; z:=b; end
    else
         if c<=b then
             begin x:=c; y:=b; z:=a; end
         else
             if c<=a then
                 begin x:=b; y:=c; z:=a; end
             else
                 begin x:=b; y:=a; z:=c; end;
write('Ciąg uporządkowany:',x:4,y:4,z:4)
end.